/**
*  Author: Magnus Hemmer Pihl
*  Student number: 5452
*
*  Assignment 2
*  16/9-2007
**/

#include <cstdlib>
#include <iostream>

#ifndef _LIST_H
#define _LIST_H
#include "List.h"
#endif

#ifndef INITIAL_SIZE
#define INITIAL_SIZE 2
#endif

using namespace std;

//Expands the capacity of the list by creating a new, larger array and re-referencing.
//Array capacity is always doubled.
void List::expand()
{
    varType *original = arr;
    int originalSize = size;
    size *= 2;
    arr = new varType[size];
    for(int i=0; i<originalSize; i++)
        arr[i] = original[i];
    delete [ ] original;
    original = NULL;
}

//Rearranges ("defragments") elements so that there are no empty spaces in the array
// between data-holding spaces.
void List::rearrange()
{
    for(int i=0; i<size; i++)
        if(arr[i] == NULL)
        {
            arr[i] = arr[i+1];
            arr[i+1] = NULL;
        }
}

//Shifts all elements of the array forward one position, starting with given position 'pos'.
//This is useful if you wish to insert data on a previously occupied position.
void List::shiftArray(int pos)
{
    if(size <= length)
        expand();
    for(int i=length-1; i>=pos; i--)
        arr[i+1] = arr[i];
    arr[pos] = NULL;
}

//Constructor. Initialized variables.
List::List()
{
    size = INITIAL_SIZE;
    arr = new varType[size];
    length = 0;
}

//Destructor. Releases memory held by array.
List::~List()
{
    delete [] arr;
    arr = NULL;		//Er vel egentlig ligemeget?
}

//Inserts data 'val' at position 'pos'.
//This will shift forward any previous data in this position, and all data following it.
void List::insert(varType val, int pos)
{
    if(pos >= 0 && pos <= length)
    {
        shiftArray(pos);
        arr[pos] = val;
        length++;
    }
}

//Erases data in position 'pos'.
//This will cause the array to be rearranged, shifting any data beyond 'pos' back one position.
void List::erase(int pos)
{
    if(pos >= 0 && pos < length)
    {
        arr[pos] = NULL;
        length--;
        rearrange();
    }
}

//Inserts data 'val' onto the first unused position (the end) of the list.
void List::push(varType val)
{
    insert(val, length);
}

//Returns and deletes the data in the last position of the list.
varType List::pop()
{
    varType val = arr[length-1];
    erase(length-1);
    return val;
}

//Returns the length (used slots - NOT array capacity!) of the list.
int List::getSize()
{
    return length;
}

//Deletes all data in the list and resizes the array to its initial size.
void List::clear()
{
    delete [] arr;
    size = INITIAL_SIZE;
    length = 0;
    arr = new varType[size];
}

//Returns 'true' if the list contains no data, or 'false' if it does.
bool List::empty()
{
    if(arr[0] == NULL)
        return true;
    return false;
}

//Returns data held at position 'pos'.
varType & List::at(int pos)
{
    if(pos <0 || pos >= length)
        pos = pos%length;
    return *(arr + pos);
}

//Operator overload for []. Equivalent of List::at(int pos).
varType & List::operator[](int pos)
{
    while(pos >= size)
        expand();
    if(pos >= length)
        length++;
    return arr[pos];
}

const varType & List::operator[](int pos) const
{
    return arr[pos];
}

//Returns a new list containing the appended data of this list, and given list 'data'.
List & List::operator+(const List &data)
{
    List *result = new List();
    for(int i=0; i < this->length; i++)
        result->push(this->arr[i]);
    for(int i=0; i < data.length; i++)
        result->push(data.arr[i]);
    return *result;
}

//Appends the content of list 'data' onto this list.
List & List::operator+=(const List &data)
{
    for(int i=0; i < data.length; i++)
        this->push(data.arr[i]);
    return *this;
}

//Checks for equality of given list 'data' and this list.
bool List::operator==(const List &data)
{
    if(this->length != data.length)
        return false;
    for(int i=0; i<this->length; i++)
        if(this->arr[i] != data.arr[i])
            return false;
    return true;
}

//See List::operator==
bool List::operator!=(const List &data)
{
    return !(this->operator==(data));
}

//Overload for output stream.
ostream &operator<<(ostream &os, const List &data)
{
    os << "{";
    for(int i=0; i<data.length; i++)
    {
        os << data.arr[i];
        if(i+1 < data.length)
            os << ", ";
    }
    os << "}";

    return os;
}